One of important processes in digital signal processing is a Fast Fourier Transformation (hereinafter, abbreviated to “FFT”) process. For example, a frequency domain equalization (FDE) technique is known as a technique for compensating for waveform distortion in signal transmission in wireless communication or wired communication. In the FDE, signal data in the time domain are transformed into data in the frequency domain by FFT, and then the transformed data are filtered for equalization. The data after the filtering are retransformed into signal data in the time domain by inverse FFT (hereinafter, abbreviated to “IFFT”) to compensate for waveform distortion of the original time-domain signal. Hereinafter, FFT and IFFT will be referred to as “FFT/IFFT” unless FFT and IFFT need to be distinguished from one another.
The FFT/IFFT processing generally includes “butterfly computation”. For example, PLT 1 discloses an FFT device using the butterfly computation. PLT 1 also discloses after-mentioned “twiddle multiplications”, that is, multiplications using twiddle factors.
The butterfly computation introduced by Cooley-Tukey, which NPL 1 discloses, is well known as an efficient FFT/IFFT processing method, for example. However, Cooley-Tukey FFT/IFFT requires complicated circuitry due to a large number of points. A Prime Factor algorithm described in NPL 2, for example, is therefore used to decompose FFT/IFFT into two smaller FFT/IFFT operations, and the FFT/IFFT processing is performed.
FIG. 6 illustrates a dataflow 500 of 64-point FFT decomposed into two-stage butterfly processing with radix-8 by using the Prime Factor algorithm, for example. The dataflow 500 includes a data rearranging process 501, 16 k times in total of radix-8 butterfly computation processes composed of butterfly computation processes 502, 503, and a twiddle multiplication process 504.
In the dataflow illustrated in FIG. 6, inputted time-domain data x(n) (n=0, 1, . . . , 63) are Fourier-transformed into frequency-domain signals X(k) (k=0, 1, . . . , 63) by FFT processing. Part of the dataflow is omitted in FIG. 6. The basic configuration of the dataflow in FIG. 6 is the same as one for IFFT processing.
If the number of points of FFT is large, circuit implementation of the entire dataflow in FIG. 6 requires huge-size circuitry. Therefore, if the number of points of FFT is large, it is common practice to use repeatedly a circuit processing part of the dataflow, depending on required processing performance, to achieve the entire FFT processing.
For example, if an FFT device, which performs FFT processing on eight pieces of data in parallel (hereinafter, referred to as “in 8-data parallel” for short) in the dataflow in FIG. 6, is formed as a physical circuit, 64-point FFT processing can be achieved by eight repeated processes in total.
The eight repeated processes, in which a process is performed in sequence for each of partial dataflows 505a to 505h performed on eight pieces of data, are performed specifically as follows. That is to say, a process corresponding to the partial dataflow 505a is performed in the first round, a process corresponding to the partial dataflow 505b is performed in the second round, and a process corresponding to the partial dataflow 505c (not shown) is performed in the third round. The subsequent processes are performed similarly in sequence up to a process corresponding to the eighth round of partial dataflow 505h. The above-mentioned processes can achieve 64-point FFT processing.
The butterfly computation includes reading data arranged sequentially in a sequence according to a predetermined rule and processing the data. This requires rearranging data in the butterfly computation. PTL 2 and PTL 3 disclose the rearrangement of data for the butterfly computation, for example. Storage means such as random access memories (RAMs) and registers is used in order to rearrange data. PTL 3 discloses the rearrangement of data using RAMs.
In signal processing such as FDE, the FFT processing is performed in blocks each of which is composed of a plurality of pieces of data. Accordingly, filtering is also performed in blocks, and therefore it is difficult to achieve adaptive filtering in which filter coefficients vary at short time intervals, for example. Therefore, it may be desirable, depending on filtering processes to be implemented, to adopt a time domain equalization (TDE) technique in which filtering for equalization is performed in time domain on signal data in time domain without transformation.
Therefore, a method can be adopted of choosing more appropriate implementation method according to filtering processing to be implemented for each of frequency-domain filtering and time-domain filtering. For example, in an optical transmission system, it can be performed to achieve compensation for linear waveform distortion by frequency-domain filtering and to achieve compensation for nonlinear waveform distortion by time-domain filtering. In addition, in some cases, the frequency-domain filtering and the time-domain filtering can be repeated a plurality of times (see PTL 4 and PTL 5, for example).
Alternatively, there is an adaptive equalization processing technique that uses frequency-domain filtering in combination with time-domain filtering (PTL 6).